#ifndef __SQBITREE_H__
#define __SQBITREE_H__

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

//类型的声明
//假设队列中的元素类型为int  
typedef int Datatype;

//树
typedef struct bitnode
{
    Datatype data;
    struct bitnode *lchild;
    struct bitnode *rchild;
    int num;
}BiTNode;

//队节点
typedef struct node
{
    //存储链表类型
    BiTNode *data;//此时存放的是一个树节点
    struct node *next;
    struct node *prev;
}Node;

//链队
typedef struct lkqueue
{ 
    //下一个入队元素的下标
    Node *rear;
    //下一个出队元素的下标
    Node *front;
    //当前队列中的元素个数
    int num;
}LkQueue;

//函数声明
/*
insertNode:往一棵二叉排序树中加入一个元素,使得二叉树任然具有排序性
@root:指针,你要把元素加入到哪一棵树
@x:你要加入的元素的值
返回值:
返回加入元素后的二叉树的根节点的地址
*/
BiTNode *insertNode(BiTNode *root,Datatype x);

/*
pre_order:以先序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/
void pre_order(BiTNode *tree);//先序排列

/*
mid_order:以中序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/ 
void mid_order(BiTNode *tree);//中序排列

/*
last_order:以后序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void last_order(BiTNode *tree);//后续排列

/*
level_order:以层次遍历的方法访问tree指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/
void level_order(BiTNode *tree);//层次排列


void orderTree(BiTNode *tree);

/*
high_tree:求树的高度
@tree:指针,指向你要遍历的二叉树的根节点
返回值:无
*/
int high_tree(BiTNode *tree);

/*删除一个节点*/
BiTNode *Delete_x_root(BiTNode *tree,Datatype x);

/*
InitQueue:初始化一个队列
返回值:返回创建好的队列的地址
*/
LkQueue *InitQueue();

/*
DestoryQueue:销毁一个队列
@q:你要销毁的队列的地址
返回值:无
*/
void DestoryQueue(LkQueue *q);

/*
ClearQueue :清空一个队列(把队列中的数据元素都清空)
@q:你要清空的队列的地址
返回值:无
*/
void ClearQueue(LkQueue *q);

/*
QueueIsEmpty:判断队列是否为空(是否存在用户数据)
@q:你要操作的队列的地址
返回值:
    返回true表示队列为空
    返回false表示队列不为空
*/
bool QueueIsEmpty(LkQueue *q);

/*
QueueSize:获取队列的大小(用户元素的个数)
@q:你要操作的队列的地址
返回值:
返回队列中当前的元素个数
*/
int QueueSize(LkQueue *q);

/*
GetHead:获取队头元素(下一次出队的元素),但是不出队列
@q:你要操作的队列的地址
@v:指针,指向一块可用的空间,用来保存队头数据的值
返回值:
    返回true表示获取成功
    返回false表示获取失败
*/
//bool GetHead(LkQueue *q,BiTNode *v);

/*
EnQueue(Push):入队列,把一个用户数据存放到队列中去(放到队尾)
@q:你要操作的队列的地址
@value:你要入队的数据
返回值:
    返回true表示入队成功
    返回false表示入队失败
*/
bool EnQueue(LkQueue *q,BiTNode *value);

/*
DeQueue(Pop):出队列,把一个用户数据从队列中拿出来(去掉队头)
@q:你要操作的队列的地址
返回值:
    返回true表示出队成功
    返回false表示出队失败
*/
bool DeQueue(LkQueue *q);

//获取队头，出队
BiTNode* dequeue(LkQueue *q);

#endif
